/*
@description:
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
*/

//自底向上递归解决（O(N)，O(N)）——类似于先序遍历
class Solution {
public:
    //辅助函数,返回节点的高度
    //注意下面返回-1表示该节点的左右子树高度差大于一，表示不可能是平衡树
    int getHeight(TreeNode * root){
	    //当前节点为空，则其高度为0
        if(root == nullptr) return 0;
	    //求左子树高度
        int leftHeight = getHeight(root->left);
        if(leftHeight == -1)    return -1;
	    //求右子树高度
        int rightHeight = getHeight(root->right);
        if(rightHeight == -1)   return -1;
        if(abs(leftHeight - rightHeight) > 1) return -1;
	    //节点高度为左右子树中较高的高度+1
        else return leftHeight > rightHeight ? leftHeight+1:rightHeight+1;
    }
    bool isBalanced(TreeNode* root) {
        // 当前节点的高度正常则说明是平衡树
        // 这里正常的定义就是不返回-1
        return getHeight(root) > -1;
    }
};

//自顶向下递归解决（O(N^2)，O(N)）——类似于后序遍历
class Solution {
public:
    // 求出当前节点的高度
    int getHeight(TreeNode * root){
        // 节点为空，高度为0
        if(root == nullptr) return 0;
        // 否则高度就是左右子节点的高度的较大值加一
        else return max(getHeight(root->left),getHeight(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        // 节点为空，必为平衡节点
        if(root == nullptr)  return true;
        // 否则只有其左右子树同时为平衡树，且左右子树高度差不大于一才是平衡树
        else {
            return abs(getHeight(root->left)-getHeight(root->right)) <= 1 && isBalanced(root->left) &&isBalanced(root->right);
    }
        }
};